import java.util.Arrays;

public class OneBitCounter_3 {

    public static int[] OneBitCount(int n){
        int[] ret = new int[n+1];
        for(int i = 1; i <= n; ++i){
            int cnt = 0;
            int tmp = i;
            while(tmp != 0){
                tmp &= (tmp - 1);
                ++cnt;
            }
            ret[i] = cnt;
        }
        return ret;
    }
    public static int[] OneBitCount1(int n){
        int[] ret = new int[n + 1];
        for(int i = 1; i <= n; ++i){
//            ret[i] = ret[i >> 1] + (i & 1);
            ret[i] = ret[(i - 1) & i] + 1;
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(OneBitCount1(10)));
    }
}
